package a13_Tree.MaxHeap;

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

/**
 * @Author quan
 * @Description 基于int的最大堆:上浮，下沉，堆化，取最大值
 * @Date 2023/3/30 16:27
 */
public class MaxHeap {
    //定义吧保存元素的数组
    private List<Integer> data;
    //堆中有效元素的个数
    private int size;
    //构造函数:如果没有给出数组容量，默认为10
    public MaxHeap(){
        this(10);
    }
    //有参构造：传入参数确定数组的容量
    public MaxHeap(int capacity){
        this.data = new ArrayList<>(capacity);
    }
    /**
     * 堆化：传入一个数组，能够还原成最大堆
     * 思想：我们可以最后的叶子节点每个都满足最大堆的要求(因为左右子树都是null)，
     * 那从不断的从最后一个不是叶子节点的 节点让它满足最大堆，也就是元素下沉，使得每个子树为堆
     */
    public MaxHeap(int[] arr){
        data = new ArrayList<>(arr.length);//创建一个和给定数组一样大小的数组
        //先将给定的数组放入堆中
        for (int i : arr ) {
            data.add(i);
            size++;
        }
        //最后一个非叶子节点，也就是最后一个节点的父节点：最后一个节点 size-1  父节点 (size-1-1)/2
        for (int i = parent(size-1); i >=0 ; i--) {
            siftDown(i);
        }
    }
    /**
     * 取出堆中的最大值
     */
    public int extractMax(){
        if(data.isEmpty()){
            throw new NoSuchElementException("heap is empty!cannot extract maxVal!");
        }
        //堆顶就是最大值
        int val = data.get(0);
        //将最后一个节点顶在根节点
        data.set(0,data.get(size-1));
        data.remove(size-1);
        size--;
        //从根节点开始下沉
        siftDown(0);
        return val;
    }
    /**
     * 向最大堆中添加元素
     */
    public void add(int val){
        //不考虑元素值的大小，直接将新元素尾插到数组的尾部
        this.data.add(val);
        size++;
        //然后调整元素的位置，使其满足最大堆的值之间的关系：元素上浮操作
        //表示最后一个添加元素的索引
        siftUp(size-1);
    }
    /**
     * 元素上浮操作：只有当还有父节点并且 当前值>父节点值，交换两者的位置
     */
    public void siftUp(int k) {
        while (k>0 && data.get(k) > data.get(parent(k))){
            //交换该节点和父节点的位置
            swap(k,parent(k));
            //继续向上判断
            k = parent(k);
        }
    }
    /**
     * 元素下沉操作：
     * ①比较当前节点的左右孩子的值，取出最大值索引记录
     * ②最大值与当前节点值进行比较：如果当前节点值大，则不需要交换位置；否则交换两者的位置,更新当前节点的索引值
     */
    public void siftDown(int k){//k是当前节点的索引,j是存储的最大值索引
        //①获取最大值索引
        // 如果只有左孩子存在，假设最大值为左孩子节点的索引
        while (leftChild(k)<size){
            int j = leftChild(k);
            //如果还有右孩子存在，比较两个节点的值大小,更新最大值的索引
            if(j+1 < size && data.get(j+1) > data.get(j)){
                j = j+1;
            }
            //②值比较
            if(data.get(k) >= data.get(j)){
                break;
            }else{
                swap(k,j);
                k = j;
            }
        }
    }
    /**
     * 交换三连
     */
    private void swap(int i, int j) {
        int temp = data.get(i);
        data.set(i,data.get(j));
        data.set(j,temp);
    }

    /**
     * 获取父节点
     */
    private int parent(int k){
        return (k-1)>>1;
    }
    /**
     * 获取左孩子
     */
    private int leftChild(int k){
        return (k<<1)+1;
    }
    /**
     * 获取右孩子
     */
    private int rightChild(int k){
        return (k<<1)+2;
    }
    /**
     * 重写toString方法:底层已经重写好了
     */
    @Override
    public String toString() {
        return this.data.toString();
    }
}
